Most network diagrams (graphs) that people use for visualization of various concepts have nodes with associated textual or graphical content. For example, in Unified Modeling Language (UML) class diagrams nodes are drawn as boxes with textual content describing class attributes or methods. As another example, in metabolic pathway diagrams nodes representing chemical compounds may have long textual labels or a graphic representation of the molecular structure.
Routing refers to paths taken by connectors to connect nodes. If edges (connectors) that are not directly connected to a particular node are drawn over that node then the label may be obscured. Alternately, if edges are drawn behind a node then the reader may erroneously assume a connection exists to the node. Routing edges around nodes avoids this ambiguity. Therefore, to automatically produce high quality drawings of network diagrams it is important to find routes for the edges that do not intersect node boundaries.
Recent work in this area involves finding shortest paths in a tangent-visibility graph. However, construction of the full tangent-visibility graph is computationally expensive, at least quadratic time in the number of nodes. This makes such existing tangent-visibility-graph routing schemes infeasible for interactive diagramming applications involving large diagrams with hundreds or thousands of nodes. Some layout algorithms, such as the level scheme for directed graphs or the topology-shape-metrics approach for orthogonal graph drawing consider edge routing as an integral step in the layout process. However, the popular force-directed family of layout algorithms for general undirected graphs does not usually consider routing edges around node hulls (except perhaps as a post-processing step). Recent work has proposed force-directed methods that are able to preserve the topology of a given edge routing, but a feasible initial routing is still found using a standard routing algorithm. For graphs with hundreds of nodes, the quadratic (in the number of nodes) or worse computational cost of constructing the visibility graph can be too slow, especially for interactive applications where the layout is changing significantly from iteration to iteration.